package com.xucy.springboot.common;


/**
 * @Author xucy
 * @Date 2019-10-22 16:23
 * @Description
 **/

public class BinarySearch {

    public static void main(String[] args) {
        System.out.println(search(new int[]{1,2,3,4,5},6));
        System.out.println(search(new int[]{1,2,3,4,5},0,4,6));
    }


    //非递归二分查找
    public static int search(int[] arr,int target){
        int low=0;
        int high=arr.length-1;

        while (low<=high){

            int mid=(low+high)/2;
            if(arr[mid]>target){
                high=mid-1;
            }else if(arr[mid]<target){
                low=mid+1;
            }else{
                return mid;
            }
        }

        return -1;
    }

    //递归二分查找
    public static int search(int[] arr,int low,int high,int target){

        if(low>high){
            return -1;
        }

        int mid=(low+high)/2;
        if(arr[mid]>target){
            high=mid-1;
            return search(arr,low,high,target);
        }else if(arr[mid]<target){
            low=mid+1;
            return search(arr,low,high,target);
        }else{
            return mid;
        }

    }
}
